This invention relates generally to a method and system for obtaining information from a plurality of remote stations.
It is a common requirement to target and possibly identify quickly one or several out of a plurality of participants according to specific selection criteria.
It is frequently required to select one or more participants according to a xe2x80x9cpriorityxe2x80x9d or xe2x80x9ccharacteristic valuexe2x80x9d based on specified selection criteria for the purpose of allocating a particular task to the participant or participants having the highest priority.
In dispatching systems, for example, for dispatching a taxi or messenger to a customer at a specified location, it is desirable that a suitable (and preferably the most suitable) taxi or messenger be sent to a particular customer. Generally the nearest, unoccupied taxi which has sufficient accommodation should be dispatched to the customer. Furthermore, it is desirable that the allocation be accomplished in the minimum possible time.
Typical existing dispatching systems include a central dispatch station having a transmitter and receiver or a transceiver in each of the participating vehicles for communicating with the central dispatch station. Typically, a voice request is transmitted by a dispatcher to each of the participating vehicles, and the dispatcher decides which of the vehicles is most suited to the task in hand based on the replies from the vehicles.
Such a system would be capable of simple implementation if the selection criteria related to static variables only. Thus, if the only selection criterion were a taxi""s current distance from the customer and each taxi were stationary, it would merely be necessary to extract the taxis"" locations once, after which it would be simple to determine which taxi were nearest to the customer""s location. However, in practice, the selection criteria relate to dynamic variables which, by definition, are changing constantly and therefore it is necessary continuously to update each taxi""s distance from the customer""s location (and/or other information required to choose a taxi for the given task) or at least to do so each time a taxi is to be dispatched.
In some typical prior art systems, this is done by providing the dispatcher with a periodically updated map that shows the respective location of each of the taxis. This updating is accomplished by the periodic transmission of a location message by each of the taxis via a communication channel. In order to ensure that the transmitted data can be received quickly and without corruption, the total spectrum width of the communication system must be very large.
In a system described in EP 0389488 job requests are dispatched by a controller to mobile vehicles which messages include information about the location of a job. Each vehicle has a receiver, transmitter and circuitry to compare the requirements of the job with the status of the vehicle. If the results of the comparison is that the vehicle is suitable for the job, then it transmits a message back to the controller volunteering itself for the job.
It should also be noted that, even in the specific case of a taxi or messenger service, distance from the customer location is by no means the only criterion according to which a task may be allocated. Thus, it may well be that the nearest messenger or taxi is already occupied and is therefore not available for performing the task. Alternatively, the nearest available taxi may not have sufficient room for carrying all the passengers to whom a taxi must be sent; or perhaps a particularly bulky load must be carried and the nearest, available taxi or messenger is inadequate for the task.
Yet a further consideration is that it is often preferred to dispatch to a customer an idle taxi waiting at the taxi rank rather than go through the process of transmitting a voice message and awaiting responses from taxis in the field prior to allocating the task to one of them. In the event that several idle taxis are waiting at the taxi rank, or where several taxis are reasonably close to the customer, it is often preferable that the taxi which has been idle for the longest period of time be selected.
Furthermore, it may not always be desirable to dispatch the nearest available taxi to a particular customer location if other customers, albeit further away, have made prior requests which have not yet been serviced.
Even apart from some of the basic limitations of prior art systems described above, it is often desirable to target and possibly to identify participants according to several selection criteria. This is somewhat analogous to performing a database search by means of key words which can be combined according to the rules of Boolean or other logic systems. However, database records are generally static and are stored at a single location. In contrast to this, the attributes of the participants that are the subject of the present invention are dynamic and constantly changing, and cannot be characterized by static data which can be stored at a single site. Thus, if the dynamic data characterizing such participants are to be searched at a single site, then the data must first be downloaded to the site where the search is to be performed. During the time that such data are downloaded, they may well change, thereby compromising the accuracy of the search which is subsequently performed.
Another application which requires the receiving and processing of information from a large number of sources is IVHS. In this application, for example, information on position and speed from a large number of vehicles is processed in order to obtain information on road delays. Again, the sending of large amounts of information requires substantial bandwidths, even though the vehicles themselves need not be identified.
Another previously unsolved problem is the tracking or mapping of the position of large numbers of vehicles. Prior solutions to this problem required the broadcasting by each vehicle of an information bearing signal including at least its position. When large numbers of vehicles are to be tracked, the amount of information to be transmitted (and the communication overhead associated with the transmission) is very large and the available time/bandwidth necessary is either unavailable or if it is available, such broadband systems are expensive. The alternative of trading bandwidth for time, results in a system which is too slow for many uses.
It is an object of some aspects of the present invention to transmit information from a plurality of remote sources without requiring that each of the transmissions be on a separate time/frequency channel.
It is an object of some aspects of the invention to provide a method of transmitting information from a plurality of remote stations wherein the information is contained in the presence or absence of a signal in a particular time and/or frequency slot and not in the identification of the particular station which transmits the information, in the transmission of an information bearing signal by the remote station and/or in how many stations transmit signals in the slot.
It is an object of some aspects of the invention to provide a method and system for determining xe2x80x9cprioritiesxe2x80x9d or xe2x80x9ccharacteristic valuesxe2x80x9d of a plurality of participants in accordance with one or more selection criteria and targeting those participants, if any, having the highest priority or the most suitable characteristic value.
It is a further object of some aspects of the invention to provide such a method and system wherein those participants having the highest priority or the most suitable characteristic value can be targeted in a short time.
Yet a further object of some aspects of the invention is to provide such a method and system wherein at least one of the targeted participants can be identified in order that a task can be allocated thereto.
Yet another object of some aspects of the invention is to provide an improved system for real time bus routing.
It is an object of some aspects of the present invention to provide a method of determining traffic delays in a road network based on transmissions from a large number of vehicles without identifying the vehicles and without receiving information associateable with a particular vehicle.
It is an object of some aspects of the present invention to provide a system for almost real time mapping of the positions of large numbers of moving stations with higher accuracy and with greater speed than prior art systems.
As used herein the term xe2x80x9cpriorityxe2x80x9d or xe2x80x9ccharacteristic valuexe2x80x9d means, in addition to its normal meaning, a characterization according to a protocol which takes into consideration one or more elements associated with a person or object being characterized.
According to a broad aspect of the invention a call is broadcast or otherwise transmitted to a plurality of remote stations. Each of the plurality of stations determines a characteristic value or priority based on certain predetermined attributes of the station and broadcasts or transmits an indication signal during a communication slot which is indicative of the characteristic value, or preferably of a range of the characteristic value. In some aspects of the invention, more than one remote station will broadcast at the same time and frequency during at least a portion of the process.
In one embodiment of the invention, all of the stations broadcast or transmit at the same frequency, i.e., all of the slots have the same frequency and the time of the slot is determined by the range of characteristic values. In a second embodiment of the invention, more than one frequency is used for communication and both the time and frequency indicate the characteristic value. In a third embodiment of the invention, all of the stations transmit at the same time, and the characteristic value is indicated by the frequency of transmission only.
It should be understood that since more than one indication signal may be broadcast or transmitted at the same time and frequency, there is no identification of the responding stations, but only an indication of the characteristics (or rather ranges of characteristics, since each time/frequency xe2x80x9cslotxe2x80x9d generally represent a range of characteristic values) which characterizes at least one remote responding station.
It should also be understood that in many preferred embodiments of the invention, the transmitted information signals are xe2x80x9cnon-information bearing signalsxe2x80x9d in that the signals per se carry no information, only the slot in which the signal occurs carries information. Information about the identity of the transmuting station may not be of present interest or alternatively, in some applications, certain slots are used only by a given remote station, whereby the broadcasting station may be identified.
According to one aspect of the invention the characteristics are one or more priorities associated with the stations.
In one aspect of the invention a control center monitors the transmissions of the remote stations and determines which of the slots having an indication signal has the highest priority. It is convenient to order the response time period into time (or time/frequency) slots each representing a range of priority values preferably in descending order of priorities. Thus, the control center need only look for the earliest slot which contains an indication signal.
Having determined the highest range of priorities which are held by at least one remote station, a second call is preferably broadcast or otherwise transmitted asking for responses only from those remote units within this range. The time or time/frequency slots are now distributed, either by a predetermined protocol or specifically by the particular call, so as to cover this range of priority values.
The stations which have priorities within this range broadcast or otherwise transmit indication signals in response to the new call in the predetermined time or time/frequency slots. This process of determining the highest range of priorities and redividing the range continues until a given criteria is met. This stage of the process often termed herein the xe2x80x9ctargeting phase,xe2x80x9d (sometimes referred to herein as the xe2x80x9cfirst phasexe2x80x9d or xe2x80x9cphase onexe2x80x9d) ends when the priority range ceases to be significant or the number of sub-ranges which are filled falls below a predetermined number based on the statistics of the total number of participating remote stations and the final range or priorities or where some other predetermined criteria is reached. At this point the number of station which are responding to the highest priority is believed to be small.
Before going on to the next stage it may be useful to estimate the number of stations which have responded to the highest priority. One method of making the estimate is by analysis of the data from the final step of phase one. A more accurate method of estimating the number of stations having the highest priority is to request each of these stations to transmit an indication signal at a randomly chosen slot over at least a portion of the entire range of time and frequency slots. Since the number of slots is now expected to be large compared to the number of stations, the number of slots which have signals is a good indication of the number of stations. An estimate of the actual number of responders is then based on the statistical relationship between the actual number of responders and the number of slots in which a signal is broadcast. If fewer stations are expected, only a single time slot may be used and only the frequency is chosen randomly by the stations.
The system then preferably initiates an xe2x80x9cidentification phasexe2x80x9d (sometimes referred to herein as xe2x80x9csecond phasexe2x80x9d or xe2x80x9cphase twoxe2x80x9d) starting with the broadcast or other transmission of an additional call requesting those stations within the highest (final) range of priorities found in the targeting phase to identify themselves. Each of the stations having a priority in this range broadcasts or otherwise transmits a signal including an identifier of the station or some other message at a slot which it chooses, preferably at random, from one of a plurality of such available slots. If only one station is expected to be within the range of priority values, then only one identification slot may be allocated. Other types of slots can also be used for the identification stage, such as coded spread spectrum signals, FDMA or CDMA. Additionally, multiple slots may be used for the same priority range to improve the reliability of detection in both the targeting and identification stages. The identification slots generally have an information carrying capacity which is larger than the slots used for indicating priorities since information (and not only an indication of the presence of a signal) is transmitted during the identification phase.
Since, when a plurality of remote stations are within the final range of values, it can be expected that more than one of the stations will respond in at least some of the slots, in which case their identification signal may be unintelligible. However, since the number of stations is relatively small, at least some of the slots will have only one identification signal. In general, the station having this signal is chosen since at this stage the difference in priority between the stations is generally unimportant. In some applications more than one identification signal may be broadcast in a particular slot, however, one signal may be clear. This station will then be chosen.
Alternatively, the stations which are left at this stage may be identified by assigning to each of the remote stations (including those which are no longer left, since the system has no indication of those which are left) a slot which is associated with only one remote station. All of the stations which are left after the previous stage are invited to broadcast in their identification slots. One or more of these responding stations is then chosen. Using this system of identification of the remote stations frees them of the need to transmit any information bearing signal, simplifying the system.
In another aspect of the invention the indication signal depends on the average velocity or delay of the remote station, which are generally vehicles. Systems which operate according to this aspect of the invention preferably broadcast a call to the remote stations which requests those stations having a delay above a given value or an average velocity below a given value to broadcast a signal indicative of their position. Such signals are then used to generate a map of those regions for which traffic is delayed or otherwise moving slowly.
Preferably, an additional call is sent to the vehicles requesting transmission of indication signals which position the slow moving or delayed vehicles at a higher resolution than that of the first call. Further calls may be made to allow for transmission of additional information on the status of the vehicles to provide further characterization of the delays.
In a preferred embodiment of the invention optimum routing of buses is made based on their positions along the route. In accordance with this embodiment, information on bus positions along the bus line is transmitted to a central dispatch station which calculates a new optimized schedule based on these updated situation reports. It should be understood that, while in general position is a two dimensional vector, the position of the bus along its route can be given by a single variable.
In a further preferred embodiment of the invention the position of a large number of vehicles can be mapped and tracked in near real time using a relatively narrow bandwidth. In this embodiment each vehicle is assigned a number of slots which are used only by that vehicle.
The vehicles must first be mapped in a preferred first, mapping, phase of the mapping and tracking procedure. In the first step of this phase, the total area of interest is divided into preferably nine areas, each of which is assigned a slot. The vehicle broadcasts a signal in the slot which corresponds to its present position. In a second step of the mapping phase, the area previously indicated as containing the vehicle is expanded to fill the nine slots. Alternatively, the area which is zoomed into the nine slots is slightly larger than the area of the previous broadcast to avoid a situation in which the vehicle was at the border of the area and left the area between steps.
This identification of one area and consequent new zooming and sub-division is repeated several times until the required resolution is achieved. The highest practical resolution, as will become clear below, is the distance that a vehicle could travel in the time it takes to perform a tracking cycle as described below. Within five iterations the individual resolution can be improved from 3.3 km to about 40 m.
In a, second, tracking phase of the mapping and tracking procedure, performed periodically after the required resolution is reached, preferably, nine slots, representing a 3xc3x973 area of resolution areas, are used to track additional movements of the vehicle. The central one of the nine areas corresponds to the area occupied by the vehicle at the end of the mapping phase (or during a previous periodic updating iteration of the tracking phase). During each periodic update, each vehicle broadcasts in a slot which corresponds to either its previous position (the slot corresponding to the center area of the 3xc3x973 group of areas) or one of the adjoining areas. In the next following iteration, the newly chosen area is the center of the 3xc3x973 matrix.
In a further preferred variation of this embodiment of the invention, only 5 slots are utilized to map into the 3xc3x973 area. One of these slots represents one of the corners (or the center) of the 3xc3x973 area and the other 4 slots represent north south or east west variations.
In a further preferred embodiment of the invention, nine areas are represented by a four bit word which is sufficient to define the 3xc3x973 matrix of elements.
In general, one or more base stations may be used for broadcasting calls and/or receiving responses from remote stations. If more than one base station is used, each station preferably performs a reduction of the data which it receives by either choosing its best candidate for performing the task or by performing a mapping function of its nearby region or of its associated vehicles. The base stations then preferably send this reduced information to a central base station which makes the final decision, constructs the desired map or performs any other final analysis. Furthermore, the central base station would, in a preferred embodiment of the invention, instruct each of the base stations as to which additional queries they should make. In this situation the subsequent queries need not be the same for all the base stations.
There is therefore provided, in accordance with a preferred embodiment of the invention, a method mapping of the characteristic values of a plurality of remote stations each having a varying attribute affecting a characteristic value computed according to a predetermined procedure comprising:
(a) assigning a plurality of transmission slots to each of the remote stations;
(b) determining, by the respective stations, of their characteristic values;
(c) initially broadcasting, by the respective stations, of their determined characteristic values in said plurality of transmission slots, said broadcast characteristic value having a first characteristic value resolution; and
(d) subsequently broadcasting, by the stations, of their respective characteristic values in said plurality of transmission slots, said subsequent broadcasting having a finer characteristic value resolution relative to said previously broadcasted characteristic value having a first characteristic value resolution.
Preferably, (d) is repeated with successively higher characteristic value resolution until the characteristic value is broadcast with a characteristic value resolution. The higher resolution preferably twice, or somewhat less than twice the first position resolution.
In a preferred embodiment of the invention, a mapping space is divided into a fixed number of portions and wherein said initial broadcast indicates which of said portions contains the position. Preferably, the initially broadcast portion or a portion somewhat larger than the initially broadcast portion is divided into a fixed number of portions of a smaller size and wherein said subsequent broadcast indicates which of said portions of smaller size contains the characteristic value.
There is further provided in accordance with a preferred embodiment of the invention, a method of tracking a characteristic value of a plurality of remote stations each having a varying attribute affecting the characteristic value computed according to a predetermined procedure, comprising:
(a) assigning a plurality of transmission slots to each of the remote stations;
(b) determining, by the respective stations, of their characteristic values relative to a previously determined characteristic value; and
(c) broadcasting, by the respective stations, of their determined characteristic values in said plurality of transmission slots, relative to the previously determined characteristic value.
Preferably the method includes iteratively repeating (b) and (c) wherein said previously determined characteristic value is the characteristic value determined in the previous iteration. Preferably, a characteristic value region surrounding said previously determined characteristic value is divided into a plurality of contiguous regions and wherein the relative characteristic value which is broadcast comprises broadcasting a signal in one or more of the transmission slots which indicates which of the regions contains the determined characteristic value. More preferably, the extent of the surrounding regions is established based on an expected maximum rate of change of the characteristic value in the remote station.
In a preferred embodiment of the invention, the previously determined characteristic value is determined in accordance with the mapping method.
A preferred embodiment of the invention includes repeating at least one step of broadcasting, at a coarser characteristic value resolution, when a valid signal is not received from a remote station during mapping or tracking.
In a preferred embodiment of the invention at least one step of broadcasting is repeated periodically to avoid accumulated errors in tracking or mapping.
In an especially useful preferred embodiment of the invention, the characteristic value is the location of a mobile remote station.